package 动态规划;

public class 最大连续子序列和 {
	public static void main(String[] args) {
		
		System.out.println(new 最大连续子序列和().maxSubArray2(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
	}
	
	public int maxSubArray(int[] array) {
		if (array == null || array.length == 0) return 0;
		int[] dp = new int[array.length];	// dp[i]表示以array[i]元素为结尾的最大连续子序列和
		dp[0] = array[0];
		int max = dp[0];
		for (int i = 1; i < array.length; i++) {
			if (dp[i - 1] <= 0) {
				dp[i] = array[i];
			} else {
				dp[i] = dp[i - 1] + array[i];
			}
			max = Math.max(max, dp[i]);
		}
		return max;
	}
	
	/**
	 * 空间复杂度优化: dp[i]的计算只考虑dp[i - 1]的值, 因此可以直接使用变量而不使用数组
	 */
	public int maxSubArray2(int[] array) {
		if (array == null || array.length == 0) return 0;
		int dp = array[0];	// dp[i]表示以array[i]元素为结尾的最大连续子序列和
		int max = dp;
		for (int i = 1; i < array.length; i++) {
			if (dp <= 0) {
				dp = array[i];
			} else {
				dp += array[i];
			}
			max = Math.max(max, dp);
		}
		return max;
	}
	
	
}
